package arithmeticSelf;

import java.util.Arrays;

public class ShellSort {
    public static void main(String[] args) {
        //定义数组--------------------
        int[] arr = new int[10];
        for (int i=0;i<arr.length;i++) {
            arr[i] = (int)(Math.random()*100)+1;
        }
        System.out.println(Arrays.toString(arr));

        //希尔排序----------------------
//        for (int gap = arr.length / 2; gap >= 1; gap /= 2) {
//            for (int i = gap; i < arr.length; i++) {
//                int temp = arr[i];
//                int j;
//                for (j = i - gap; j >= 0; j -= gap) {
//                    if (arr[j] > temp) {
//                        arr[j + gap] = arr[j];
//                    } else {
//                        break;
//                    }
//                }
//                arr[j+gap] = temp;
//            }
//        }
//        System.out.println(Arrays.toString(arr));

        //-------------------------------------------
        for (int gap = arr.length / 2; gap >= 1; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                int temp = arr[i];
                int j = i - gap;
                for (; j >= 0; j -= gap) {
                    if (arr[j] > temp) {
                        arr[j + gap] = arr[j];
                    } else {
                        break;
                    }
                }
                arr[j + gap] = temp;
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}
